package 剑指offer;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Offer41_JZ63 {
    // 使用快排法

    static List<Integer> list = new ArrayList<>();

    public static void Insert(Integer num) {
        list.add(num);
    }

    public static Double GetMedian() {
        int length = list.size();
        int[] arr = new int[length];
        for(int i=0; i<list.size(); i++) {
            arr[i] = (int)list.get(i);
        }

        if(length % 2 == 1) {
            return (double) getForIndex(arr, length/2);
        } else {
            int[] arr2 = new int[arr.length];
            System.arraycopy(arr, 0, arr2, 0, arr.length);
            return ((double)getForIndex(arr, length/2 - 1) +
                    (double)getForIndex(arr2, length/2)) / 2;
        }
    }

    public static int getForIndex(int[] arr, int index) {
        int start = 0;
        int end = arr.length - 1;
        int res = partion(arr, start, end);
        while(res != index) {
            if (res < index) {
                start = res + 1;
                res = partion(arr, start, end);
            } else {
                end = res - 1;
                res = partion(arr, start, end);
            }
        }
        return arr[res];
    }

    public static int partion(int[] arr, int start, int end) {
        int pivot = arr[start];
        while(start < end) {
            while (start<end && arr[end]>=pivot) {
                end--;
            }
            arr[start] = arr[end];
            while (start<end && arr[start]<=pivot) {
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = pivot;
        return start;
    }

    // 使用大根堆小根堆法
    static PriorityQueue<Integer> minQueue = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1.compareTo(o2);
        }
    });
    static PriorityQueue<Integer> maxQueue = new PriorityQueue<>(new Comparator<Integer>() {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });

    public static void insert2(Integer num) {
        if (((minQueue.size()+maxQueue.size()) % 2) == 0) {
            if (maxQueue.size()>0 && num<maxQueue.peek()) {
                maxQueue.add(num);
                num = maxQueue.poll();
            }
            minQueue.add(num);
        } else {
            if (minQueue.size()>0 && num>minQueue.peek()) {
                minQueue.add(num);
                num = minQueue.poll();
            }
            maxQueue.add(num);
        }
    }

    public static Double GetMedian2() {
        int length = minQueue.size() + maxQueue.size();
        if (length % 2 == 0) {
            return ((double)minQueue.peek() + (double)maxQueue.peek()) / 2;
        } else {
            return (double)minQueue.peek();
        }
    }

    public static void test() {
        list.add(5);
        System.out.println(GetMedian());
        list.add(2);
        System.out.println(GetMedian());
        list.add(3);
        System.out.println(GetMedian());
        list.add(4);
        System.out.println(GetMedian());
        list.add(1);
        System.out.println(GetMedian());
    }

    public static void test2() {
        insert2(5);
        System.out.println(GetMedian2());
        insert2(2);
        System.out.println(GetMedian2());
        insert2(3);
        System.out.println(GetMedian2());
        insert2(4);
        System.out.println(GetMedian2());
        insert2(1);
        System.out.println(GetMedian2());
    }

    public static void main(String[] args) {
        test2();
    }

}
